Существует много вариантов алгоритма А*. Пол [1222] предложил использовать в алгоритме А* динамическое взвешивание (dynamic weighting), в котором в качестве функции оценки применяется взвешенная сумма текущей длины пути и эвристической функции, а не просто сумма. Веса корректируются динамически по мере развития поиска. Можно доказать, что алгоритм Пола является е-допустимым (т.е. гарантирует нахождение решений с отклонением от оптимального решения на коэффициент 1+е), где 8 — параметр, предусмотренный в алгоритме. Таким же свойством обладает алгоритм[ 1188], который способен выбрать из периферии любой узел, при условии, что его f-стоимость находится в пределах коэффициента 1+е от стоимости периферийного узла с наименьшей f-стоимостью. Выбор соответствующего коэффициента может быть сделан таким образом, чтобы существовала возможность минимизировать стоимость поиска.

Алгоритм А* и другие алгоритмы поиска в пространстве состояний тесно связаны с методами ветвей и границ, которые широко используются в исследованиях операций [901]. Соотношения между алгоритмами поиска в пространстве состояний и методами ветвей и границ были глубоко исследованы в [867], [869], [1115]. Мартелли и Монтанари [990] показали связь между динамическим программированием (см. главу 17) и некоторыми типами поиска в пространстве состояний. Кумар и Канал [868] предприняли попытку "великой унификации" методов эвристического поиска, динамического программирования, а также методов ветвей и границ под общим названием CDP (Composite Decision Process — комплексный процесс принятия решений).

Поскольку компьютеры в конце 1950-х — начале 1960-х годов имели не больше нескольких тысяч слов оперативной памяти, темой ранних исследовательских работ часто служил эвристический поиск с ограничением памяти. Одна из самых первых программ поиска, Graph Traverser [404], фиксирует свои результаты в виде некоторого оператора после выполнения поиска по первому наилучшему совпадению вплоть до заданного предела объема памяти. Алгоритм IDA* [835], [836] стал одним из первых широко применяемых оптимальных алгоритмов эвристического поиска с ограничением памяти, после чего было разработано большое количество его вариантов. Анализ эффективности алгоритма IDA* и сложностей, возникающих при его применении с эвристическими функциями, которые встречаются в реальных задачах, приведен в работе Патрика и др. [1182].